Typical example of bipartite graph is a graph obtained from a collection of documents presented as a term $\times$ document matrix.
The reader should be familiar with k-means algorithm and spectral graph partitioning theory and algorithms.
The reader should be able to apply spectral partitioning of bipartite graphs to data clustering problems.
Credits. The notebook is based on I. Mirošević, Spectral Graph Partitioning and Application to Knowledge Extraction.
Undirected bipartite graph $G$ is a triplet $G=(T,D,E)$, where $T=\{t_{1},\cdots ,t_{m}\}$ and $D=\{d_{1},...,d_{n}\}$ are two sets of vertices and $E=\{(t_{i},d_{j}):t_{i}\in R,d_{j}\in D\}$, is a set of edges.
$G$ is weighted if there is weight $\omega(e)$ associated with each edge $e\in E$.
For example, $D$ is a set of documents, $T$ is a set of terms (words) and edge $e=(t_{i},d_{j})$ exists if document $d_{j}$ contains term $t_{i}$. Weight $\omega(e)$ can be number of appearances of the term $t_i$ in the document $d_j$.
A term-by-document-matrix is a matrix $A\in\mathbb{R}^{m\times n}$ with $A_{ij}=\omega((t_i,d_j))$.
The weight matrix of $G$ is $W=\begin{bmatrix}0 & A \\ A^{T} & 0 \end{bmatrix}$.
The Laplacian matrix of $G$ is $$L=\begin{bmatrix} \Delta_{1} & -A \\ -A^{T} & \Delta_{2}\end{bmatrix},$$ where $\Delta_1$ and $\Delta_2$ are diagonal matrices with elements $\Delta_{1,ii}=\sum\limits_{j=1}^n A_{ij}$ for $i=1,\ldots,m$, and $\Delta_{1,jj}=\sum\limits_{i=1}^m A_{ij}$ for $j=1,\ldots,n$.
The normalized Laplacian matrix of $G$ is $$L_n=\begin{bmatrix} I & -\Delta_{1}^{-\frac{1}{2}}A\Delta_{2}^{-\frac{1}{2}} \\ -\Delta_{2}^{-\frac{1}{2}}A^T\Delta_{1}^{-\frac{1}{2}} & I \end{bmatrix} \equiv \begin{bmatrix} I & -A_n \\ -A_n^T & I \end{bmatrix}. $$
Let $\lambda$ be an eigenvalue of $L_n$ with an eigenvector $w=\begin{bmatrix} u \\ v\end{bmatrix}$, where $u\in \mathbb{R}^{m}$ $v\in\mathbb{R}^{n}$. Then $L_n w=\lambda w$ implies $A_n v =(1-\lambda)u$ and $A_n^T u=(1-\lambda)v$. Vice versa, if $(u,\sigma,v)$ is a singular triplet of $A_n$, then $1-\sigma$ is an eigenvalue of $L_n$ with (non-unit) eigenvector $w=\begin{bmatrix} u \\ v\end{bmatrix}$.
The second largest singular value of $A_n$ corresponds to the second smallest eigenvalue of $L_n$, and computing the former is numerically more stable.
Bipartitioning algorithm is the following:
Recursive bipartitioning algorithm is the following:
Multipartitioning algorithm is the following:
In [1]:
# Some packages
using LightGraphs
using GraphPlot
using Clustering
In [2]:
# Some functions
using SparseArrays
using LinearAlgebra
function my_weight_matrix(src::Array,dst::Array,weights::Array)
n=nv(G)
sparse([src;dst],[dst;src],[weights;weights],n,n)
end
my_laplacian(W::AbstractMatrix)=spdiagm(0=>vec(sum(W,dims=2)))-W
function my_normalized_laplacian(L::AbstractMatrix)
D=1.0./sqrt.(diag(L))
n=length(D)
[L[i,j]*(D[i]*D[j]) for i=1:n, j=1:n]
end
Out[2]:
In [3]:
# Sources, targets, and weights
n=7
dn=[6,6,7,6,7,7]
tn=[1,2,2,3,4,5]
wn=[3,1,3,2,2,3]
[dn tn wn]
Out[3]:
In [4]:
mynames=["Term 1";"Term 2";"Term 3";"Term 4";"Term 5";"Doc 1";"Doc 2"]
Out[4]:
In [5]:
G=Graph(n)
for i=1:length(dn)
add_edge!(G,tn[i],dn[i])
end
gplot(G, nodelabel=mynames, edgelabel=wn)
Out[5]:
In [6]:
W=my_weight_matrix(tn,dn,wn)
Out[6]:
In [8]:
Matrix(W)
Out[8]:
In [9]:
L=my_laplacian(W)
Matrix(L)
Out[9]:
In [10]:
Ln=my_normalized_laplacian(L)
Out[10]:
In [11]:
A=W[1:5,6:7]
Δ₁=sqrt.(sum(A,dims=2))
Δ₂=sqrt.(sum(A,dims=1))
An=[A[i,j]/(Δ₁[i]*Δ₂[j]) for i=1:size(A,1), j=1:size(A,2)]
Out[11]:
In [13]:
# The partitioning - explain the results!
U,σ,V=svd(An)
Out[13]:
In [14]:
U[:,2]
Out[14]:
In [15]:
V[:,2]
Out[15]:
In [16]:
using Plots
In [17]:
import Plots.spy
spy(A)=heatmap(A, yflip=true, color=:heat, aspectratio=1)
Out[17]:
In [18]:
# Define sizes
using Random
m=[200,100,100]
n=[100,200,100]
density=[0.5,0.7,0.4]
A=Array{Any}(undef,3)
Random.seed!(421)
for i=1:3
# Generate sparse random
A[i]=sprand(m[i],n[i],density[i])
end
B=blockdiag(A[1],A[2],A[3])
Out[18]:
In [19]:
spy(Matrix(B))
Out[19]:
In [20]:
# The structure of singular vectors reflects the blocks
using Arpack
S,rest=svds(B,nsv=3)
Out[20]:
In [21]:
# S is a structure
S.S
Out[21]:
In [22]:
# Plot the first three left singular vectors
k=size(B,1)
x=collect(1:k)
scatter(x,S.U[:,1:3])
Out[22]:
In [23]:
S.V
Out[23]:
In [24]:
# Plot the first three right singular vectors
scatter(x,S.V)
Out[24]:
In [25]:
# Add random noise
noise=sprand(k,k,0.3)
C=B+noise
spy(Matrix(C))
Out[25]:
In [26]:
# Apply random permutation to rows and columns of C
using Random
D=C[randperm(k),randperm(k)]
spy(Matrix(D))
Out[26]:
Question. Given D, can we recover C?
Answer. Yes (with spectral partitioning)!
In [27]:
S,rest=svds(D,nsv=3)
Out[27]:
In [28]:
# K-means on rows of U
outU=kmeans(Matrix(transpose(S.U)),3)
Out[28]:
In [29]:
S.Vt
Out[29]:
In [30]:
# K-means on Vt
outV=kmeans(S.Vt,3)
Out[30]:
In [31]:
sortperm(outV.assignments)
Out[31]:
In [32]:
E=D[sortperm(outU.assignments),sortperm(outV.assignments)]
spy(Matrix(E))
Out[32]:
In [ ]: